#ifndef QUEUE_H_
#define QUEUE_H_



#include <iostream>
using namespace std;

template<class Type> class Queue;
template<class Type> ostream& operator<<(ostream&, const Queue<Type>&);
template<class Type> class QueueItem;
template<class Type> class Queue {
	friend ostream& operator<< <Type>(ostream&, const Queue<Type>&);

public:
	Queue<Type>() :
		_front(0), _back(0) {
	}
	~Queue();
	Type remove();
	void add(const Type&);
	bool is_empty() const {
		return _front == 0;
	}

private:
	QueueItem<Type>* _front;
	QueueItem<Type>* _back;
};

template<class Type> class Queue;
template<class Type> ostream& operator<<(ostream&, const QueueItem<Type>&);
template<class Type> class QueueItem {
	friend class Queue<Type>;
	friend ostream& operator<< <Type>(ostream& os, const QueueItem<Type>&);

	QueueItem() :
		_item(0), _next(0) {
	}

public:
	QueueItem<Type>* next() {
		return _next;
	}

private:
	Type _item;
	QueueItem<Type>* _next;
};


template<class Type> void Queue<Type>::add(const Type& val) {
	QueueItem<Type>* pt = new QueueItem<Type>(val);
	if (is_empty())
		_front = _back = pt;
	else {
		_back->_next = pt;
		_back = pt;
	}
}

template<class Type> Type Queue<Type>::remove() {
	if (is_empty()) {
		cerr << "remove() on empty queue\n";
		exit(-1);
	}

	QueueItem<Type>* pt = _front;
	_front = _front->_next;

	Type retval = pt->_item;
	delete pt;
	return retval;
}





template<class Type> class Queue;
template<class Type> class QueueItem;
template<class Type> ostream& operator<<(ostream &os, const Queue<Type> &q) {
	os<<"<";
	QueueItem <Type>* p;
	for (p = q._front; p; p = p->next())
		os << *p << " ";
	os << " >";
	return os;
}

template<class Type> class QueueItem;
template<class Type> ostream& operator<<(ostream &os, const QueueItem<Type> &qi) {
	os<< qi._item;
	return os;
}

#endif /*QUEUE_H_*/
